class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        st = {}
        t = set()

        def search(node):
            if not node.left and not node.right:
                out = [node.val]
                out_t = tuple(out)
                if out_t in st:
                    t.add(st[out_t])
                else:
                    st[out_t] = node
            else:
                left = [None]
                right = [None]
                if node.left:
                    left = search(node.left)
                if node.right:
                    right = search(node.right)
                out = [node.val] + left + right
                out_t = tuple(out)
                if out_t in st:
                    t.add(st[out_t])
                else:
                    st[out_t] = node
            return out

        search(root)
        return list(t)
